package cn.bellychang.leetcode.question617;

/**
 * You are given two binary trees root1 and root2.
 * Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
 * You need to merge the two trees into a new binary tree.
 * <p>
 * The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node.
 * Otherwise, the NOT null node will be used as the node of the new tree.
 *
 * @author ChangLiang
 * @date 2021/2/8
 */
public class Solution {

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {

        return merge(root1, root2);
    }

    public TreeNode merge(TreeNode treeNode1, TreeNode treeNode2) {

        if (treeNode1 == null && treeNode2 == null) {
            return null;
        }
        if (treeNode1 == null && treeNode2!=null) {
            return treeNode2;
        }
        if (treeNode2 == null && treeNode1!=null) {
            return treeNode1;
        }
        TreeNode curr = new TreeNode(treeNode1.val + treeNode2.val);
        curr.left = merge(treeNode1.left, treeNode2.left);
        curr.right = merge(treeNode1.right, treeNode2.right);
        return curr;
    }
}
